#include<iostream>
#include<cmath>
#include<string>
using namespace std;

class Solution {
public:
    string multiply(string num1, string num2)
    {
        const int N = 1000;
        int a[N] = { 0 }, b[N] = { 0 }, c[N] = { 0 };
        int l1, l2, l3;
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        l1 = num1.size(); l2 = num2.size(); l3 = l1 + l2;
        for (int i = 0; i < l1; i++)a[i] = num1[i] - '0';
        for (int i = 0; i < l2; i++)b[i] = num2[i] - '0';

        for (int i = 0; i < l1; i++)
        {
            for (int j = 0; j < l2; j++)
            {
                c[i + j]+= a[i] * b[j];//无进位相乘
            }
        }

        for (int i = 0; i < l3; i++)//处理余数
        {
            c[i + 1] += c[i] / 10;
            c[i] %= 10;
        }

        while (l3 > 1 && c[l3 - 1] == 0)l3--;//清除前导零
        string result;
       
        for (int i = 0; i < l3; i++)
        {
           result += (c[i] + '0');
        }
        reverse(result.begin(), result.end());
        return result;
        
    }
};


class Solution2 {
public:
    string multiply(string num1, string num2) {
        vector<int>tmp(num1.size() + num2.size() - 1, 0);
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        for (int i = 0; i < num1.size(); i++)//利用无进位相乘
        {
            for (int j = 0; j < num2.size(); j++)
            {
                tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');
            }
        }
        string ret; int carry = 0;
        for (int i = 0; i < tmp.size(); i++)
        {
            int sum = tmp[i] + carry;
            ret.push_back(sum % 10 + '0');
            carry = sum / 10;
        }
        if (carry)ret.push_back(carry + '0');
        while (ret.back() == '0' && ret.size() > 1)ret.pop_back();//去除前导0
        reverse(ret.begin(), ret.end());
        return ret;
    }
};